﻿#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

class Solution {
private:
    const int inf = 1 << 30;
    map<char, int> cnt;
    map<char, int> ori;
public:
    bool check() {
        for (auto& pair : ori) {
            char key = pair.first;
            int right_cnt = pair.second;
            if (cnt[key] < right_cnt) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        for (auto c : t) ori[c]++;
        int sp = 0, ep = 0;
        int min_width = inf, minL = -1;
        while (ep < s.length()) {
            char c = s[ep];
            if (ori.count(c) != 0)  //t中有这个字符，只是优化性能吧
                cnt[c]++;
            while (check()) {     //收缩
                int clength = ep - sp + 1;
                if (clength < min_width) {
                    min_width = clength;
                    minL = sp;
                }
                cnt[s[sp]]--;
                sp++;
            }
            ep++;
        }
        if (minL == -1) return "";
        else return s.substr(minL, min_width);
    }
};

Solution solution;

int main() {
    string s = "cabwefgewcwaefgcf", t = "cae";
    cout << solution.minWindow(s, t) << endl;
    return 0;
}